//1370. 上升下降字符串
//思路：本题的本质其实是对s中的字符单个先按升序排，直到最大被排到尾
//再按降序单个排，直到最小被排到尾
//不断重复上两步，直到整个字符串被用完，这时，将他们拼接起来即可
//方法：使用计数排序就可以，因为字符串都是小写字符，因此只要26个大小的数组

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string sortString(string s) 
    {
        vector<int> hash(26, 0);
        for(auto ch : s)
        {
            hash[ch-'a']++;
        }

        string ans;
        while(ans.size() < s.size())//当返回的字符串长度 >= s的长度就停止
        {
            for(int i = 0; i < 26; i++)
            {
                if(hash[i])
                {
                    ans += (i+'a');
                    hash[i]--;//每次该位置-1处理。避免重复
                }
            }
            for(int i = 25; i >= 0; i--)
            {
                if(hash[i])
                {
                    ans += (i+'a');
                    hash[i]--;
                }
            }
        }
        return ans;
    }
};